The recent U.S. FCC auctions in electromagnetic spectrum have kindled interest in mechanisms that allocate bundles of discrete, complementary resources, and is of direct relevance to e-commerce applications. The FCC and its consultants expected that the licensees would see significant synergies from operating the same spectrum bands in geographically contiguous regions of the country, or contiguous bands in the same region. However, the mechanism designers employed by the FCC developed the Simultaneous Ascending Auction (SAA) (McMillan, 1994; McAfee and McMillan, 1996), which received very positive press when it generated billions of dollars of revenue for the U.S. government. The SAA allocates resources by operating a first-price auction for each resource. The auctions are synchronized, and the mechanism enforces an eligibility constraint that restricts bidders from bidding on more items than they had “active” bids (i.e. winning or newly submitted) in the previous round.
However, recent studies have shown that combinatorial auctions, which permit bids on combinations of items, can perform significantly better than the SAA. It is well known that when bidders have complementary preferences, price equilibria may not exist. That is, there may not be prices on individual objects that support the optimal allocation. One example is reproduced in Table 1. The efficient allocation is indicated with an asterisk.
TABLE 1An example without equilibrium prices for individual goods.ABABBidder 1003*Bidder 22 2 2 
Economists have studied the conditions under which price equilibria exist. For example, it has been shown that price equilibria exist if a gross substitutability condition holds (Kelso and Crawford, 1982), or if utility functions satisfy the no-complementarities condition (Gul and Stacchetti). Bikhchandani and Mamer (1997) demonstrated that equilibria exist if the total value of the solution to the discrete allocation problem is equal to the value of the corresponding relaxed linear optimization problem. In these cases, a simple market structure in which each object is sold in independent auctions can lead to the efficient outcome.
When the above conditions do not hold, we must resort to more complex auction mechanisms to achieve the desired outcomes. The benchmark allocation mechanism is the Generalized Vickrey Auction (GV A).
Generalized Vickrey Auction
The GVA is an incentive compatible, efficient, and individually rational direct revelation mechanism. Each bidder submits its utility function, and the auction computes the optimal allocation and charges each bidder a payment. The bidder's payment, πi, is the impact that its presence has on the welfare of the other bidders.πi=V(f*(I/i))−[V(f*)−vi(fi*)],where f*(I/i) is the optimal solution to the problem of allocating the resources when i is excluded, V is the total valuation of the indicated solution, and vi is bidder i's valuation for the resources allocated to it in the indicated solution.
The GVA extends the intuition gained from Vickrey's (1961) seminal work, and results by Clarke (1971) and Groves (1973) in general allocation problems. The mechanism's incentive compatibility property follows from the fact that its bid determines what the bidder gets, but not how much it pays (or receives).
The GVA has several drawbacks that inhibit its use in practice. The main imperfection of the GVA is that it is not budget-balanced. It may be necessary for the auctioneer to subsidize the auction in order to get both buyers and sellers to bid truthfully.
A second weakness, highlighted by Banks et al. (1989) is that the GVA requires that each participant specify her utility function, which (potentially) requires that she report 2n−1 values. If the preferences cannot be expressed in a compact form, this requirement may make the GVA impractical. In addition, when participants reveal their true preferences they may leave themselves open to manipulation by an unscrupulous auctioneer (seller). For example, a common manipulation used by sellers in an English auction involves using a “shill” who tries to bid up the highest bidder even after the second highest real bidder has dropped out.
In many cases it may be costly for bidders to determine their true valuations for every possible combination of items, the majority of which play no role in determining the solution. Parkes et al. (1998) argue that the cognitive costs of accurately determining one's true valuation is a major factor in the predominance of the English auction online—a participant needs an accurate appraisal of its value for a good only if it is still in the running near the end of the auction.
A third objection to using the GVA in practice is that, even in the one-sided case, it computes discriminatory payments. That is, if, at the end of the auction, the auctioneer were to announce the allocations and payments computed by the mechanism, some bidder may desire another's bundle. This can be seen in the example in Table 2, in which the items A and B could be two different units of the same resource.
TABLE 2An example in which the GVA payments are discriminatory.ABABBidder 15*5 7Bidder 25 5*8
The GVA payments are π1=$3, and π2=$2. Even though (by incentive compatibility) no course of action would have made bidder 1 better off than truth-telling, he would still envy bidder 2.
Combinatorial Auction Designs
Several alternatives to the GVA have been suggested. One major distinction among the candidates is whether or not they allow bundle bids.
The motivation for permitting bundle bidding is to combat the exposure problem (Rothkopf et al., 1998). Without bundle bids, bidders who have superadditive valuations are forced to either bear risk or bid over-cautiously. Suppose, for example, bidder i has a valuation for the bundle AB that exceeds the sum of its value for A and B alone. If bidder i offers no more for either A or B than their individual values, the bidder may fail to purchase the bundle even when the combined cost is under its valuation. On the other hand, if i is less conservative, it can offer more than its value for one of the goods. The strategy exposes the bidder to potential losses if, in the end, it gets only one item and pays more than its value for that individual item.
Allowing bundle bids introduces the free rider problem (Rothkopf et al., 1998), in which bidders buying smaller bundles need to collaborate to displace a larger bundle bidder. Consider the situation where bidder 1 values A at $5, bidder 2 values B at $4, and bidder 3 values AB at 7. Suppose bidder 3 has offered $6 for AB. Neither bidder 1 nor bidder 2 can displace bidder 3 without taking a loss. In order to displace bidder 3, the two bidders have to collaborate. However, the more that bidder 2 bids, the less bidder 1 will have to contribute to displace bidder 3. The same logic holds for bidder 2. Thus, the two bidders have an incentive to free ride on each other, which could lead to a coordination failure and an inefficient outcome.
Banks et al. (1989) proposed an iterative mechanism, called the Adaptive User Selection Mechanism (AUSM), that allows bundle bids. AUSM posts the current best allocation on a bulletin board visible to all of the participants. To become part of the current best allocation, a new bid has to offer more than the sum of all of the bids it displaces. Bids that are not part of the best allocation are posted in a publicly-displayed standby queue designed to facilitate the coordination of two or more smaller bidders combining on a new bid large enough to displace a larger bidder. However, posting bids on a standby queue reveals information about the bidders that they may prefer not to reveal.
Both SAA and AUSM have complex strategy spaces and have so far proved intractable to game-theoretic analysis. Ledyard et al. (1997) executed a series of controlled experiments to investigate the performance of three mechanisms: sequential ascending bid auctions, the SAA, and AUSM. In problems the authors classified as “hard”—involving significant complementarities and a range of solutions—AUSM significantly outperformed the other two mechanisms. This led the authors to conclude that, when there are complementarities, mechanisms that allow package bidding will perform better. This seems to have been taken to heart by the FCC and its consultants, and the current recommendation is that the FCC should explore mechanisms that allow bidders to bid on bundles (CRA, 1998).
Recently, Demartini et al. proposed the Resource Allocation Design (RAD) (DeMartini et al., 1998), which combines features of AUSM and SAA. RAD allows bidders to place bids on bundles, then computes the locally efficient allocation. In this situation, the locally efficient allocation is also revenue maximizing.
A linear program is solved to generate approximate prices, and a beat-the-quote rule is used. Bidders need to maintain eligibility by continuing to win items, or by submitting new bids.
In experimentation with Cal Tech students, RAD averaged more efficient solutions in fewer iterations than either AUSM or SAA. However, RAD has shortcomings of its own. One problem that plagued both SAA and RAD was that some bidders lost money. This turned out to be a side effect of the eligibility rule. In order to maintain eligibility in future rounds, participants often placed low bids on items they didn't really want, but which they ended up winning anyway. A second drawback of RAD is that the prices computed by the linear program are not guaranteed to be separating prices. This makes it difficult for bidders to determine whether they are winning.
Another ascending auction that is being investigated is iBundle (Parkes, 1999). iBundle allows bids on bundles and computes the locally efficient allocation. It associates payments with bundles, in effect, announcing a payment lattice as a price quote. There are three variations of iBundle, which differ based on the manner in which payments are computed: iBundle(2) announces anonymous payments to every bidder, iBundle(3) announces discriminatory payments, and iBundle(d) announces discriminatory payments for some bidders, and anonymous payments for the rest. In all three versions, the auction ends when no bidders submit new bids, and the winners pay the price for their bid.
In both RAD and iBundle, the winners pay the exact amount of their bids. In general, charging bidders their bids has an undesirable property, namely, that it may not correspond to a payment equilibrium—at the final payments, a bidder may wish to purchase a bundle other than the one allocated.
Consider a simple example where bidder 1 has bid $5 for A, $4 for B, and $7 for the bundle AB. Bidder 2 offers $2 for A, $3 for B, and $6 for AB. The bids are diagrammed in Table 3.
TABLE 3An example in which charging bid payments is not an equilibrium.ABABBidder 15*47Bidder 22 3*6
The optimal allocation assigns A to bidder 1 and B to bidder 2. Suppose we have reached the end of the auction and that these bids actually represent the bidders' true valuations for the items. If we charge each bidder its bid, then bidder 1 will pay $5 for A, and bidder 2 will pay $3 for B. At these payments, bidder 1 would rather buy B than A, because that would provide her with a surplus of $1, whereas purchasing A for $5 leaves her no surplus.
The U.S. patent to Ausubel U.S. Pat. No. 5,905,975 discloses a dynamic combinatorial auction system which allows for combinations of items. The system runs a very large number of simultaneous ascending auctions which results in the GVA prices. Thus, the Ausubel's system does not produce uniform prices which can be revealed to all of the participants.
The following U.S. patents are only generally related to the present invention: Barzilai et al. U.S. Pat. No. 6,012,045; Shavit et al., U.S. Pat. No. 4,799,156; and Godin et al., U.S. Pat. No. 5,890,118.